package com.swak.algs;

/**
 * 
 * 位图： 是通过位来标志状态的一种方式, 需要预先知道大小
 * 
 * @author lifeng
 */
public class Code08 {

	/**
	 * 
	 * @author lifeng
	 */
	static class BitMap {

		long[] bits;

		BitMap(int max) {
			/*
			 * 至少有一个1长度， 其实就是: max / 64 + 1
			 */
			bits = new long[(64 + max) >> 6];
		}

		/**
		 * 标记一个位置的状态
		 * 
		 * @param status
		 */
		void mark(int num) {

			/*
			 * 1. num >> 6  计算块偏移（除）
			 * 2. num & 63  计算块内偏移（取余）
			 * 3. 1L << num & 63 设置第几位为 1 状态
			 * 4. | 添加状态
			 * 
			 * ==========》  byte[2] 存一个 7：存在第 0 块， 块内偏移是 7
			 * 00000000 00000000
			 * 
			 * 00000111 >> 3	==> 0
			 * 00000111 & 0000111	==> 7
			 * 1b << 7 = 10000000
			 * byte[0] |= 10000000;
			 * 
			 */
			bits[num >> 6] |= (1L << (num & 63));
		}

		/**
		 * 是否存在这个数
		 * 
		 * @param num
		 * @return
		 */
		boolean has(int num) {
			return ((bits[num >> 6] >>> (num & 63)) & 1L) == 1;
		}

		/**
		 * 清除当前位置的状态
		 * 
		 * @param num
		 */
		void clear(int num) {
			bits[num >> 6] &= ~(1L << (num & 63));
		}

		/**
		 * 打印
		 */
		void print() {
			for (long num : bits) {
				print(num);
			}
		}

		/**
		 * 打印
		 */
		void print(long num) {
			for (int i = 0; i < 64; i++) {
				System.out.print(((num >>> i) & 1L) == 0 ? '0' : '1');
			}
			System.out.println("\t");
		}
	}

	public static void main(String[] args) {
		BitMap bitMap = new BitMap(1);
		bitMap.mark(0);
		bitMap.print();
		System.out.println(bitMap.has(0));
	}
}
